vzdelanifandomcom-20200214-history
36SPA Speciální architektury
Obecně z architekury počítačů Vysvětlete rozdíl mezi zásobníkovou a střadačovou architekturou. Rozdíl spočívá uložení operandu. Zásobníková architektura ukládá operandy na vrchol zásobníku, instrukce pak provádí operace nad zásobníkem, např. A+B proběhne jako PUSH A, PUSH B, ADD, tedy sečtení dvou čísel na vrcholu zásobníku, výsledek je uložen na vrcholu. Střadačová architektura ukládá operandy do registru (střadač, akumulátor). Operace A+B by se mohla provést například takto: LD mem_A ; uložím obsah paměti do registru ACC ADD mem_B ; ACC := ACC + mem_B ST vysledek ; uloží obsah ACC na adresu vysledek Výsledek sčítáni je uložen v akumulátoru. Napsat program pro zásobníkový počítač který spočte a*a*(b+4*a)+3*2 Uvedený výraz a*a*(b+4*a)+3*2 je nutné nejprve převést do postfixové notace: a a b 4 a * + * * 3 2 * + Poté už je možné napsat program pro zásobníkovou ISA, protože pořadí operací je dané postfixovým výrazem: PUSH a PUSH a PUSH b PUSH 4 PUSH a MUL ; 4*a ADD ; 4*a + b MUL ; (4*a + b) * a MUL ; (4*a + b) * a * a PUSH 3 PUSH 2 MUL ; 3 * 2 ADD ; 3 * 2 + (4*a + b) * a * Nyní je na vrcholu zásobníku uložena vypočtená hodnota výrazu. Jaké znáte typy kódování instrukcí? U každého uveďte jeho výhody a nevýhody. Který typ kódování používají RISC procesory a proč? * Instrukce s proměnlivou délkou kódu: délka operačního znaku instrukce se liší (např. u 80x86 od 1 do 17 bytů). Výhody: šetří paměť, často používané instrukce můžou mít krátší kód. * Instrukce s pevnou délkou kódu: používá se u RISCových architektur s pipelinou. Výhody: instrukce jsou v paměti zarovnané, jednodušší dekodér operačního znaku. Jaké adresní módy pro přistup k operandům jsou charakteristické pro 32-bitové procesory RISC? Mohou všechny instrukce použivat všechny adr. mody? Jaké instrukce daný adresní mód požaduji? * Registrový: operandy umístěné v redistrech (add r4, r3) * Přímý (Immediate): operand součástí op. znaku instukce (add r4, 666) * Displacement: k hodnotě registru se přičítá číslo pro zjištění adresy (mov eax, esp+4) * Registrový nepřímý: registr obsahuje adresu s uložením operandu (mov edx, eax) * Indexový: např. přístup k polím, jeden registr obsahuje adresu, druhý index (mov eax, edi+ecx) * Přímý nebo absolutní: parametrem je absolutní adresa (mov eax, 0x08048380) * Paměťový nepřímý: operand instukce je adresa, na které leží další adresa na které je... * Autoincrement/Autodecrement: po provedení instukce se hodnota ukazatele automaticky změní, hodí se pro průchod polem v cyklu * Scaled: např. hodnota indexového registru roste po jedné a násobí se velikostí proměnné (např. * 4) Použítí adresačních módu v instrukcích závisí na ISA, obecně největší možnosti adresování mají instrukce pro přesun dat. Jakým způsobem bývají realizovány instrukce podm. skoku v souborech instrukci? Kolik instrukci je třeba k realizaci podmínky a skoku, jak je proveden test (3 moznosti)? * Condition Code: operace v ALU nastaví příznaky a podle toho je proveden skok (2 instrukce). * Condition Register: Výsledek výrazu se zapíše do registru. Tento registr je operandem intrukce pro vuhodnocení a skok (2 instrukce). * Compare and Branch: Porovnání je součástí skokové instrukce (1 instrukce). K cemu se pri beznem provadeni programu pouziva zasobnik? Kde a jakym zpusobem byvaji tyto zasobniky implementovany. Uved vice zpusobu. * Alokace lokálních proměných, dá se k nim pak přistupovat relativně vzhledem k base pointeru nebo stack pointeru. * Volání fukcí, kdy data jsou předávána přes zásobník (stack frame), záleží na Aplication Binary Interface daného operačního systému. * Skok do podprogramu, na zásobník se uloží hodnota "PC+1" (návratová adresa). * Provedení obsluhy přerušení při volání přerušení, uloží se aktuální stav registů a příznaků plus návratová adresa. * Přepínání kontextu v OS s podporou preemptivního multitaskingu. Zde se ukládají na zásobník hodnoty registrů, příznaků, segmentové registry a hodnota program counteru. Zásobník je obvykle umístěn v hlavní paměti. Záleží na implementaci zda bude růst nahoru nebo dolů. Požadavky na procesory pro všeobecné použití a specializované. * Architektura přístupu do paměti: von Neumannovská nebo hardvardská (vyskytuje se u specializovaných). * Architektura procesoru: zásobníková, střadačová, registrová, pipeliny, superskalární. * Instrukční sada: RISC, CISC, instrukce provádějící speciální operace v HW, SIMD, FPU, vektorové instrukce, rychlé přepínání kontextu. * Přístup do paměti: chráněný režim, stránkování, segmentace, cache (L1, L2), zarovnání, vícebránová paměť. * Přístup k perifériím: přes porty, mapované v hlavní paměti, kombinované, DMA. Jak je na procesoru Cell realizován součet dvou 64bitových čísel? První číslo uloženo v registrech 20 a 21, druhé číslo v registrech 22 a 23, výsledek v registrech 30 a 31: a 31,21,23 ; sečtení spodních částí cg 30, 21, 23 ; výpočet carry (přenosu) addx 30, 20, 22 ; součet horních části + carry Normalizujte výraz y = 5*a - 2*b pro výpočet na fixed point aritmetice v rozsahu -1,1, když a je v rozsahu -10, 10 a číslo b je v rozsahu -100,100. Nejprve musíme určit rozsah proměnné y'' tím, že postupně dosadíme všechny kombinace mezí proměnných ''a a b''. Pro ''y nám vyjde rozsah -250 až 250. Každou proměnnou vydělíme a vynásobíme jejím rozsahem (tím zůstane rovnice v platnosti): (y/250)*250 = 5*(a/10)*10 - 2*(b/100)*100 Rovnici vydělíme rozsahem proměnné y'': (y/250) = 0.2*(a/10) - 0.8*(b/100) Před začátkem výpočtu musí být proměnné ''a a b'' normalizovány. Po výpočtu normalizovaný výsledek převedeme na ''y. Navrhněte funkční bloky a datové cesty pro zásobníkově orientovaný procesor (ústní) Turingův stroj (ústní) Definice Turingův stroj je šestice M=(Q, \Gamma, s, b, F, \delta) kde : * Q je konečná množina vnitřních stavů * \Gamma je konečná abeceda symbolů a znaků * s\in Q je počáteční stav * b\in \Gamma je symbol reprezentující prázdný symbol ( b neni součástí vstupní abecedy přijímaného řetězce) * F\subseteq Q je množina koncových stavů * \delta: Q\times\Gamma\rightarrow Q\times(\Gamma \cup \{L,R\}) přechodová funkce, kde: ** L znamená posun čtecí hlavy vlevo ** R znamená posun čtecí hlavy vpravo Výpočet Na začátku výpočtu je Turingův stroj v počáteční konfiguraci a na pásce je zapsané vstupní slovo. Dále pracuje v jednotlivých krocích: # pokud je aktuální stav zároveň stavem koncovým, výpočet končí # čtecí hlava přečte jeden vstupní symbol z buňky, na které se právě nachází # pokud je v přechodové funkci pro aktuální stav a přečtený symbol definovaný přechod, provede se (v případě více možných přechodů u nedeterministických strojů se vybere jeden náhodně): #* změní se stav #* na aktuální pozici hlavy se zapíše příslušný symbol #* hlava se příslušným způsobem posune Heslo Tringův stroj na Wikipedii Technologie MMX a 3DNow! Jak se liší součet se saturací od standardního součtu a v čem je jeho význam? Bez saturace dojde k přetečení a tím se např. ze součtu 2 kladných čísel může stát záporné (při práci s barvami z bílé -> černá). U saturace to nehrozí, výsledek je nejvýš roven maximálnímu rozsahu čísla (dáno velikostí registru). S jakými dat.typy pracuje technologie 3DNow!? Instrukční sada 3DNow! od AMD používá registry MMX (mm0 ... mm7), které mohou obsahovat: 8x packed byte, 4x packed word, 2x packed dword, AMD přidalo instrukce po podporu operací v pohyblivé řadové čárce a do 64bitového MMX registru si ukládá 2x číslo single precision (32bitů dle IEEE 754). Výpočet odmocniny na 3DNow! Jelikož je k dispozici pouze instrukce PFRSQRT pro výpočet hodnoty 1/\sqrt{x} , je pro výpočet druhé mocniny nutno provést x \cdot 1/\sqrt{x} = \sqrt{x} . Máme na výběr s jakou přesností se výpočet provede, zde pro 15 bitů: MOVD mm0, mem; mm0 := {0, x} PFRSQRT mm1, mm0 ; mm1 := {1/sqrt(x), 1/sqrt(x)} PUNPCKLDQ mm0, mm0 ; mm0 := {x, x} PFMUL mm0, mm1 ; mm0 := {x*1/sqrt(x), x*1/sqrt(x)} Výpočet s větší přesností (24 bitů) využívá navíc instrukce PFRSQIT1 a PFRSQIT2, ty provádějí první a druhou iteraci Newtnovy-Raphsonovy metody. MOVD MM0, mem; 0 | a PFRSQRT MM1, MM0 ; 1/(sqrt a) | 1/(sqrt a) (approx.) MOVQ MM2, MM1 ; X_0 = 1/(sqrt a) (approx.) PFMUL MM1, MM1 ; X_0 * X_0 | X_0 * X_0 step 1 PUNPCKLDQ MM0, MM0 ; a | a (MMX instr.) PFRSQIT1 MM1, MM0 ; (intermediate) step 2 PFRCPIT2 MM1, MM2 ; 1/(sqrt a) (full precs.t)ep 3 PFMUL MM0, MM1 ; (sqrt a) | (sqrt a) Příklad pack/unpack instrukce u MMX. * Pack instrukce: např.: PADDxx pro sečtení dvou registrů, podle suffixu xx se volí instrukce pro určitý datový typ a nebo pro saturovanou aritmetiku. * Unpack instrukce: PAND provede bitový AND dvou MMX registrů. 3DNow: registry, jak se principielně spočte 1/x, (téma k ústní) Instrukční soubor 3DNow! neobsahuje instrukce pro dělení, musí se použít instrukce PFRCP pro výpočet obrácené hodnoty dělitele (1/x) a ta se pak vynásobí s dělencem y * (1/x). Příklad výpočtu dělení: MOVD mm0, mem0 ; mm0 := { 0.0, x } PFRCP mm0, mm0 ; mm0 := { 1/x, 1/x } MOVQ mm1, mem1 ; mm1 := { z, y } PFMUL mm0, mm1 ; mm0 := { z * 1/x, y * 1/x} Výpočet s větší přesností (24 bitů) využívá navíc instrukce PFRCPIT1 a PFRSCPIT2, ty provádějí první a druhou iteraci Newtnovy-Raphsonovy metody. Instrukční sada MMX (téma k ústní) Celočíselné 64 bitové registry mm0..mm7, sdílí se s registry FPU (st0...st7), což znemožňuje společné použití znaménkových a MMX instrukcí. Celkem 57 instrukcí, 4 nové datové typy (packed byte, packed word, packed double word, quad word). Funkce pracující s MMX registry musí po skončení práce tyto registry vynulovat pomocí instrukce EMMS. EMMS je také nutné provést před volánimi a návraty (call a ret), procesory AMD mají v rozšíření 3DNow! instrukci FEMMS, která to samé provádí rychleji. Instrukce EMMS nutná pro přepnutí z MMX do floating point vyžaduje asi 50 taktů. S MMX registry spolupracují rozšíření AMD pojmenované 3DNow!, 3DNow! Extensions (3DNow!+) a 3DNow! MMX Extensions (MMX+). Digitální signální procesory Vyjmenujte adresační způsoby, které jsou typicky implementované v DSP procesorech (včetně použití). Adresační způsoby v DSP pracují nad proudem dat -- vzorků, které jsou uloženy za sebou a může jích být nekonečně mnoho, data se ukládájí do kruhového bufferu. Při uložení dat se zkontroluje, zda ukazatel ukazuje na konec bufferu, pokud ne nastaví svoji adresu na danou hodnotu, pokud ano nastaví svojí adresu na začátek. * Lineární: data jsou uložena postupně za sebou * Modulo: pro přístup do kruhového bufferu * Modulo s libovolnou bází: pro přístup do kruhového bufferu * Bit-reversing: slouží k implementaci FFT a motýlku, kde se mění adresy tak, že se obrátí pořadí bitů (000 => 000, 001 => 100, 010 => 010, 011 => 110, ...) * Post-increment/decrement: změna adresy po provedení instrukce * Pre-increment/decrement: změna adresy před provedením instrukce Jaké operace se v DSP typicky provádějí paralelně? load z paměti (po 2 sběrnicích ze 2 pamětí), výpočet v ALU (násobení a sčítání) Nakreslete strukturu aritmeticke jednotky DSP Soubor:Dsp_alu.png DSP instrukce, rozdíl oproti GP procesorům U DSP není kladen tak veliký důraz na přesnost, operace s desetinými čísly bývají implementovány s pevnou řadovou čárkou (fixed point) s různou přesností (12, 24, 32, 40, bitů). Protože DSP jsou určeny k realtimových aplikacím není u aritmetických operací řešení výjimek a přetečení, aritmetika používa saturaci (pokud výsledek přeteče velikost registru, je uložena maximální možná hodnota). Často používaným typem instrukce je multiply-accumulate. Protože se při implementaci filtrů klade velký důraz na násobení, jsou v DSP obsaženy rychlé násobičky. pametovy system u DSP procesoru Typický digitální signální procesor je vystavěn na harvardské architektuře. Tato architektura má oproti von Neumannovu modelu počítače oddělenou paměť pro program od paměti pro data. V praxi to znamená, že data a kód programu využívají vlastní sběrnice, což zvyšuje propustnost systému. Typické použití DSP procesorů, filtry, FFT (téma k ústní) * Zpracování obrazů: zahrnuje tiskárny, audio/video, kamery (provádí konvoluci), digitální kamery (výpočty pro JPEG, MPEG). * Komunikace: telefonie a datové sítě (TDMA, CDMA, GSM), zpracování signálu v síťových prvcích * Automobily: populární procesor Motorola MPC555, je nutno zparcovávat množství informací v reálném čase Neuronové sítě a neuročipy Jaké metriky jsou dostupné u neuročipu ZISC36? max |xi-pi| a suma |xi-pi| Jaké jsou odezvy neuročipu pro body A,B,C,D? Nakreslen obrázek s obdélníkovými oblastmi kategorií neuronů a vyznačenými body takto: bod A ležel jen v 1 obdélníku kat.2, bod B ve 2 obdélnících kat.1 a 2, bod C ve 2 obdélnících-oba kat.1 a bod D ležel mimo obdélníky klasifikace A: klasifikován, kat.2; klasifikace B: neklasifikován (různé kategorie aktivních neuronů-1 a 2); klasifikace C: klasifikován, kat.1; klasifikace D: neklasifikován, žádný aktivní neuron Nejdříve naučíme neurochip ZISC36 naučeno na nějaká data pro kategorii A, pak nějaký neuron zareaguje i na data pro kategorii B, co se v učícím módu stane? Hádám: neuron, který se stal aktivním na těchto datech kategorie B, může být sám kategorie B - pak by se nestalo nic, pokud je ovšem jiné kategorie, pak musí redukovat NAIF (jakési pole citlivosti). Nakreslete schéma analogového zapojení neuronu. Jakou funkce f(x) toto zapojení implementuje? Soubor:Neur_ana.gif Architektura VLIW a Itanium Jak jsou v procesoru Itanium ošetřeny výjimky? Ppovídání o řídící spekulaci ld.s,NaT bitu/NaTVal,což umožňuje,že výjimka ve větvi,kterou nakonec nepoužijeme,nám program neovlivní,kontrola funkcí chk.s a případný recovery kód při výjimce Proč nemá Itanium NaT bit u FP registrů? NaT (Not a Think) -- indikace výjimky, u obecných registů se ukládá v 65. bitu. Výjimka je generována při běžných aritmetických operacích a je přenášena až k výsledku. FP registry pracují s pohyblivou řád.čárkou, kde existují speciální kombinace mantisy a exponentu takové, že se nejedná o číslo (NaN), či jde o +/- nekonečno atd. -- tento NAN se užije jako NaT, bit navíc by byl zcela zbytečný. Napsat jak vypadá instrukce pro VLIW, který bude mít jednu branch unit, 4x integer unit a jednu FP unit Kde se dnes používá architektura VLIW? Uveďte alespoň dva příklady. * Procesor Intel Itanium * Procesor Crusoe od Transmety má vnitřní architektury VLIW, ale díky vestavěnému binary-binary překladači umožňuje běh x86 binárek. * Některé DSP procesory Max.pocet skoku v VLIW instrukci staci napsat "1" a 3b jsou doma :-) Architektura VLIW, principy, proč se VLIW používá u DSP, princip paralelizace u architektury VLIW. (ústní) Intel Itanium: popis a další věci (ústní) IA-64 je vytvořen v RISCovém stylu, instrukční sada registr-registr, ale obsahuje navíc podporu pro kompilátory a paralelismus na úrovni instrukcí (ILP -- Instruction Level Paralelism). Instukční slovo je dlouhé 128 bitů (3x 41 bitů + 5 bitů). Registry: * 128x 64bitových registrů (mají ve skutečnosti 65 bitů), registry 0-31 jsou vždy použitelné, registry 32-127 tvoří registrový zásobník, který se posouvá při skoku do podprogramu. * 128x 82bit. FP registrů obsahující 2 bity navíc v části pro exponent v porovnání s 80bitovým formátem IEEE * 64x 1bit predicate registrů p0...p63, nastavují je porovnávací instrukce a slouží k podmíněnému provádění instrukcí * 8x 64bitové skokové registry využívaní pro nepřímé skoky * množství dalších registrů pro ovládání systému, mapování paměti, čitačů a komunikaci s OS Instrukční paralelismus: * Implicitní: instukce jsou do skupin, každá skupina neobsahuje datové závislosti nebo jiné důvody pro vnik hazardů. * Explicitní Dataflow Nakreslete dataflow graf pro výraz: y=a+3*b-4 Jednoduchý obrázek:vstupy 3 a b vstupují do uzlu MUL, a a výstup tohoto uzlu MUL vstupují do uzlu ADD a nakonec výstup uzlu ADD a vstup 4 vstupují do uzlu SUB-jeho výstup je výsledkem. Na jakém typu dataflow počítače je možné realizovat následující kód? N = read(input); for(i = 0; i < 10; ++i){ for(j = 0; j < N; ++j){ a = a + 1; } } Rozdíl mezi statickým a dynamickým dataflow. Statický - Pešek: , cílová hrana> Dynamický - Pešek , vstupní hrana> Dynamický umožnujě výpočet cyklů (zavislých na nějaké proměnné). Nakreslete dataflow graf pro y=a*a+3*b-4. K cemu je matching unit u dynamickeho dataflow? Matching Unit obsahuje pešky, kteří čekají na své partnery stejné barvy (poměrně rozsáhlá asociativní paměť) Nezařazené Uveďte příklady instrukcí bytecodu, které lze plně hardwarově realizovat a které nikoliv. * Lze realizovat v HW: aritmet./log.operace se základními dat.typy(int,char,pointer...),jednodušší práce s poli * Nelze: práce s objekty (založení new, volání metod)